<!DOCTYPE HTML>
<html lang="en" >
    
    <head>
        
        <meta charset="UTF-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <title>红黑树 | python 数据结构与算法</title>
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="generator" content="GitBook 2.6.7">
        
        
        <meta name="HandheldFriendly" content="true"/>
        <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
        <meta name="apple-mobile-web-app-capable" content="yes">
        <meta name="apple-mobile-web-app-status-bar-style" content="black">
        <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
        <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">
        
    <link rel="stylesheet" href="../gitbook/style.css">
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-highlight/website.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-search/search.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-fontsettings/website.css">
        
    
    

        
    
    
    <link rel="next" href="../六大排序/六大基本排序.html" />
    
    
    <link rel="prev" href="../树的实现/B+树.html" />
    

        
    </head>
    <body>
        
        
    <div class="book"
        data-level="2.3"
        data-chapter-title="红黑树"
        data-filepath="树的实现/红黑树.md"
        data-basepath=".."
        data-revision="Mon Jun 10 2019 17:10:15 GMT+0800 (中国标准时间)"
        data-innerlanguage="">
    

<div class="book-summary">
    <nav role="navigation">
        <ul class="summary">
            
            
            
            

            

            
    
        <li class="chapter " data-level="0" data-path="index.html">
            
                
                    <a href="../index.html">
                
                        <i class="fa fa-check"></i>
                        
                        python数据结构与算法
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1" >
            
            <span><b>1.</b> 剑指offer</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.1" data-path="剑指offer/补码.html">
            
                
                    <a href="../剑指offer/补码.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.1.</b>
                        
                        补码
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="剑指offer/剑指offer1-24题.html">
            
                
                    <a href="../剑指offer/剑指offer1-24题.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.2.</b>
                        
                        剑指offer1-24题
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="剑指offer/剑指offer25-43题.html">
            
                
                    <a href="../剑指offer/剑指offer25-43题.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.3.</b>
                        
                        剑指offer25-43题
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="2" data-path="树的实现/树的定义.html">
            
                
                    <a href="../树的实现/树的定义.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.</b>
                        
                        各种树
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="2.1" data-path="树的实现/B-树.html">
            
                
                    <a href="../树的实现/B-树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.1.</b>
                        
                        B-树
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="树的实现/B+树.html">
            
                
                    <a href="../树的实现/B+树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.2.</b>
                        
                        B+树
                    </a>
            
            
        </li>
    
        <li class="chapter active" data-level="2.3" data-path="树的实现/红黑树.html">
            
                
                    <a href="../树的实现/红黑树.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.3.</b>
                        
                        红黑树
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="3" >
            
            <span><b>3.</b> 六大排序</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="3.1" data-path="六大排序/六大基本排序.html">
            
                
                    <a href="../六大排序/六大基本排序.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.1.</b>
                        
                        六大基本排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="3.2" data-path="六大排序/快速排序.html">
            
                
                    <a href="../六大排序/快速排序.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.2.</b>
                        
                        快速排序
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="4" >
            
            <span><b>4.</b> 算法的介绍</span>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="4.1" data-path="算法的介绍/字典序算法.html">
            
                
                    <a href="../算法的介绍/字典序算法.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.1.</b>
                        
                        字典序算法
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="4.2" data-path="算法的介绍/布隆算法.html">
            
                
                    <a href="../算法的介绍/布隆算法.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.2.</b>
                        
                        布隆算法
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    


            
            <li class="divider"></li>
            <li>
                <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
                    Published with GitBook
                </a>
            </li>
            
        </ul>
    </nav>
</div>

    <div class="book-body">
        <div class="body-inner">
            <div class="book-header" role="navigation">
    <!-- Actions Left -->
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href="../" >python 数据结构与算法</a>
    </h1>
</div>

            <div class="page-wrapper" tabindex="-1" role="main">
                <div class="page-inner">
                
                
                    <section class="normal" id="section-">
                    
                        <h2 id="&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#xFF08;bst&#xFF09;&#x5177;&#x5907;&#x4EC0;&#x4E48;&#x7279;&#x6027;&#x5462;&#xFF1F;">&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#xFF08;BST&#xFF09;&#x5177;&#x5907;&#x4EC0;&#x4E48;&#x7279;&#x6027;&#x5462;&#xFF1F;</h2>
<ol>
<li><p>&#x5DE6;&#x5B50;&#x6811;&#x4E0A;&#x6240;&#x6709;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x5747;&#x5C0F;&#x4E8E;&#x6216;&#x7B49;&#x4E8E;&#x5B83;&#x7684;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x3002;</p>
</li>
<li><p>&#x53F3;&#x5B50;&#x6811;&#x4E0A;&#x6240;&#x6709;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x5747;&#x5927;&#x4E8E;&#x6216;&#x7B49;&#x4E8E;&#x5B83;&#x7684;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x3002;</p>
</li>
<li><p>&#x5DE6;&#x3001;&#x53F3;&#x5B50;&#x6811;&#x4E5F;&#x5206;&#x522B;&#x4E3A;&#x4E8C;&#x53C9;&#x6392;&#x5E8F;&#x6811;&#x3002;</p>
</li>
</ol>
<p>&#x4E0B;&#x56FE;&#x4E2D;&#x8FD9;&#x68F5;&#x6811;&#xFF0C;&#x5C31;&#x662F;&#x4E00;&#x9897;&#x5178;&#x578B;&#x7684;&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#xFF1A;</p>
<p><img src="images/&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;.png" alt="img"></p>
<p>&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#x7684;&#x601D;&#x60F3;&#xFF1A;&#x67E5;&#x627E;&#x6240;&#x9700;&#x7684;&#x6700;&#x5927;&#x6B21;&#x6570;&#x7B49;&#x540C;&#x4E8E;&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#x7684;&#x9AD8;&#x5EA6;&#x3002;</p>
<p>&#x5728;&#x63D2;&#x5165;&#x8282;&#x70B9;&#x7684;&#x65F6;&#x5019;&#x4E5F;&#x662F;&#x5229;&#x7528;&#x7C7B;&#x4F3C;&#x7684;&#x65B9;&#x6CD5;&#xFF0C;&#x901A;&#x8FC7;&#x4E00;&#x5C42;&#x4E00;&#x5C42;&#x6BD4;&#x8F83;&#x5927;&#x5C0F;&#xFF0C;&#x627E;&#x5230;&#x65B0;&#x8282;&#x70B9;&#x5408;&#x9002;&#x63D2;&#x5165;&#x7684;&#x4F4D;&#x7F6E;&#x3002;</p>
<p>&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#x4E5F;&#x5B58;&#x5728;&#x7F3A;&#x9677;&#xFF1A;</p>
<p>&#x5047;&#x8BBE;&#x521D;&#x59CB;&#x7684;&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#x53EA;&#x6709;&#x4E09;&#x4E2A;&#x8282;&#x70B9;&#xFF0C;&#x6839;&#x8282;&#x70B9;&#x503C;&#x4E3A;9&#xFF0C;&#x5DE6;&#x5B69;&#x5B50;&#x503C;&#x4E3A;8&#xFF0C;&#x53F3;&#x5B69;&#x5B50;&#x503C;&#x4E3A;12&#xFF1A;</p>
<p><img src="images/&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;1.png" alt="img"></p>
<p>&#x63A5;&#x4E0B;&#x6765;&#x6211;&#x4EEC;&#x4F9D;&#x6B21;&#x63D2;&#x5165;&#x5982;&#x4E0B;&#x4E94;&#x4E2A;&#x8282;&#x70B9;&#xFF1A;7,6,5,4,3&#x3002;&#x4F9D;&#x7167;&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#x7684;&#x7279;&#x6027;&#xFF0C;&#x7ED3;&#x679C;&#x4F1A;&#x53D8;&#x6210;&#x4EC0;&#x4E48;&#x6837;&#x5462;&#xFF1F;</p>
<p><img src="images/&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;2.png" alt="img"></p>
<p>&#x6B63;&#x662F;&#x5982;&#x6B64;&#xFF0C;&#x8FD9;&#x6837;&#x7684;&#x5F62;&#x6001;&#x867D;&#x7136;&#x4E5F;&#x7B26;&#x5408;&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#x7684;&#x7279;&#x6027;&#xFF0C;&#x4F46;&#x662F;&#x67E5;&#x627E;&#x7684;&#x6027;&#x80FD;&#x5927;&#x6253;&#x6298;&#x6263;&#xFF0C;&#x51E0;&#x4E4E;&#x53D8;&#x6210;&#x4E86;&#x7EBF;&#x6027;&#x3002;</p>
<p>&#x90A3;&#x4E48;&#x4E3A;&#x4E86;&#x89E3;&#x51B3;&#x591A;&#x6B21;&#x63D2;&#x5165;&#x65B0;&#x8282;&#x70B9;&#x800C;&#x5BFC;&#x81F4;&#x7684;&#x4E0D;&#x5E73;&#x8861;&#xFF0C;&#x7EA2;&#x9ED1;&#x6811;&#x5C31;&#x5E94;&#x8FD0;&#x800C;&#x751F;&#x4E86;&#x3002;</p>
<p>&#x4E0D;&#x5747;&#x8861;&#x7684;&#x60C5;&#x51B5;&#x4F1A;&#x4E25;&#x91CD;&#x5F71;&#x54CD;&#x641C;&#x7D22;&#x6548;&#x7387;&#x3002;&#x5C06;2-3&#x6811;&#x7684;&#x601D;&#x60F3;&#x94FA;&#x5F00;&#xFF0C;&#x80FD;&#x591F;&#x5F97;&#x5230;2-3-4&#x6811;&#x3002;&#x8FD9;&#x6B21;&#x8981;&#x8BF4;&#x7684;&#x662F;&#x7EA2;&#x9ED1;&#x6811;&#xFF0C;&#x7EA2;&#x9ED1;&#x6811;&#x662F;&#x6839;&#x636E;2-3-4&#x6811;&#x7684;&#x601D;&#x60F3;&#xFF0C;&#x5BF9;2-3-4&#x6811;&#x8FDB;&#x884C;&#x5B9E;&#x73B0;&#x3002;&#x5148;&#x6765;&#x770B;&#x770B;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x6837;&#x5B50;&#x3002;</p>
<hr>
<p>&#x4E0B;&#x56FE;&#x4E2D;&#x8FD9;&#x68F5;&#x6811;&#xFF0C;&#x5C31;&#x662F;&#x4E00;&#x9897;&#x5178;&#x578B;&#x7684;&#x7EA2;&#x9ED1;&#x6811;&#xFF1A;</p>
<p><img src="images/&#x7EA2;&#x9ED1;&#x6811;.png" alt="img"></p>
<hr>
<p>&#x7EA2;&#x9ED1;&#x6811;&#x548C;2-3-4&#x6811;&#x7684;&#x5173;&#x7CFB;&#xFF1A;</p>
<p>&#x7EA2;&#x8272;&#x8282;&#x70B9;&#x53EF;&#x4EE5;&#x770B;&#x4F5C;&#x662F;&#x4E0E;&#x5176;&#x7236;&#x8282;&#x70B9;&#x7EC4;&#x6210;&#x7684;&#x591A;&#x5143;&#x8282;&#x70B9;&#xFF0C;&#x6BD4;&#x5982; 3 &#x53F3;&#x5B50;&#x6811;&#x662F; 4&#xFF0C;4&#x662F;&#x7EA2;&#x8272;&#xFF0C;&#x6240;&#x4EE5;&#x53EF;&#x4EE5;&#x770B;&#x4F5C;&#x662F; 3&#xFF0C;4&#x591A;&#x5143;&#x8282;&#x70B9;</p>
<p><img src="images/2-3-4&#x6811;.png" alt="img"></p>
<p>&#x6309;&#x7167;&#x4E0A;&#x9762;&#x7684;&#x7EA2;&#x9ED1;&#x6811;&#x4E0E;2-3-4&#x6811;&#x7684;&#x5173;&#x7CFB;&#xFF0C;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x8FD9;&#x6837;&#x6765;&#x770B;&#x7EA2;&#x9ED1;&#x6811;&#xFF1A;</p>
<p><img src="images/2-3-4&#x6811;&#x4E0E;&#x7EA2;&#x9ED1;&#x6811;.png" alt="img"></p>
<p><strong>Red Black Tree &#x7EA2;&#x9ED1;&#x6811; </strong>&#x662F;&#x4E00;&#x79CD;&#x81EA;&#x5E73;&#x8861;&#x7684;&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#xFF0C;&#x5403;&#x4E86;&#x7B26;&#x5408;&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;&#x7684;&#x57FA;&#x672C;&#x7279;&#x6027;&#x5916;&#xFF0C;&#x5B83;&#x8FD8;&#x5177;&#x6709;&#x4E0B;&#x5217;&#x7684;&#x9644;&#x52A0;&#x7279;&#x6027;&#xFF1A;</p>
<ol>
<li><p>&#x8282;&#x70B9;&#x662F;&#x7EA2;&#x8272;&#x6216;&#x9ED1;&#x8272;&#x3002;</p>
</li>
<li><p>&#x6839;&#x8282;&#x70B9;&#x662F;&#x9ED1;&#x8272;&#x3002;</p>
</li>
<li><p>&#x6BCF;&#x4E2A;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x90FD;&#x662F;&#x9ED1;&#x8272;&#x7684;&#x7A7A;&#x8282;&#x70B9;&#xFF08;NIL&#x8282;&#x70B9;&#xFF09;&#x3002;</p>
</li>
<li><p>&#x6BCF;&#x4E2A;&#x7EA2;&#x8272;&#x8282;&#x70B9;&#x7684;&#x4E24;&#x4E2A;&#x5B50;&#x8282;&#x70B9;&#x90FD;&#x662F;&#x9ED1;&#x8272;&#x3002;(&#x4ECE;&#x6BCF;&#x4E2A;&#x53F6;&#x5B50;&#x5230;&#x6839;&#x7684;&#x6240;&#x6709;&#x8DEF;&#x5F84;&#x4E0A;&#x4E0D;&#x80FD;&#x6709;&#x4E24;&#x4E2A;&#x8FDE;&#x7EED;&#x7684;&#x7EA2;&#x8272;&#x8282;&#x70B9;)</p>
</li>
<li><p>&#x4ECE;&#x4EFB;&#x4E00;&#x8282;&#x70B9;&#x5230;&#x5176;&#x6BCF;&#x4E2A;&#x53F6;&#x5B50;&#x7684;&#x6240;&#x6709;&#x8DEF;&#x5F84;&#x90FD;&#x5305;&#x542B;&#x76F8;&#x540C;&#x6570;&#x76EE;&#x7684;&#x9ED1;&#x8272;&#x8282;&#x70B9;&#x3002;</p>
</li>
</ol>
<h3 id="&#x7ECF;&#x8FC7;&#x4E0A;&#x9762;&#x7684;&#x5B9A;&#x4E49;&#xFF0C;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x53D1;&#x73B0;&#x4E0B;&#x9762;&#x51E0;&#x4E2A;&#x4E8B;&#x5B9E;&#xFF1A;">&#x7ECF;&#x8FC7;&#x4E0A;&#x9762;&#x7684;&#x5B9A;&#x4E49;&#xFF0C;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x53D1;&#x73B0;&#x4E0B;&#x9762;&#x51E0;&#x4E2A;&#x4E8B;&#x5B9E;&#xFF1A;</h3>
<ol>
<li><p>&#x4E24;&#x4E2A;&#x7EA2;&#x8282;&#x70B9;&#x4E0D;&#x80FD;&#x76F8;&#x8FDE;</p>
</li>
<li><p>&#x4ECE; x &#x5230; x &#x7684;&#x540E;&#x4EE3;&#x53F6;&#x8282;&#x70B9;&#x7684;&#x8DEF;&#x5F84;&#x4E0A;&#xFF0C;&#x9ED1;&#x8272;&#x8282;&#x70B9;&#x7684;&#x6570;&#x91CF;&#x662F;&#x76F8;&#x540C;&#x7684;&#x3002;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x628A;&#x8FD9;&#x4E2A;&#x6570;&#x91CF;&#x5B9A;&#x4E49;&#x79F0;&#x4E3A; bh(x). &#x5176;&#x4E2D;&#x4E0D;&#x5305;&#x542B;x&#x3002;</p>
</li>
<li><p>&#x4ECE;&#x8DDF;&#x8282;&#x70B9;&#x5230;&#x53F6;&#x8282;&#x70B9;&#x7684;&#x957F;&#x5EA6;&#x5DEE;&#x4E0D;&#x4F1A;&#x8D85;&#x8FC7;&#x4E00;&#x500D;&#x3002;</p>
</li>
<li><p>&#x5305;&#x542B;n&#x4E2A;&#x5185;&#x90E8;&#x8282;&#x70B9;&#x7684;&#x7EA2;&#x9ED1;&#x6811;&#xFF0C;height &lt;= 2log(n+1)</p>
</li>
</ol>
<p>&#x6B63;&#x56E0;&#x4E3A;&#x8FD9;&#x4E9B;&#x89C4;&#x5219;&#x9650;&#x5236;&#xFF0C;&#x624D;&#x4FDD;&#x8BC1;&#x4E86;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x81EA;&#x5E73;&#x8861;&#x3002;&#x7EA2;&#x9ED1;&#x6811;&#x4ECE;&#x6839;&#x5230;&#x53F6;&#x5B50;&#x7684;&#x6700;&#x957F;&#x8DEF;&#x5F84;&#x4E0D;&#x4F1A;&#x8D85;&#x8FC7;&#x6700;&#x77ED;&#x8DEF;&#x5F84;&#x7684;2&#x500D;&#x3002;</p>
<p>&#x5F53;&#x63D2;&#x5165;&#x6216;&#x5220;&#x9664;&#x8282;&#x70B9;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x89C4;&#x5219;&#x6709;&#x53EF;&#x80FD;&#x88AB;&#x6253;&#x7834;&#xFF0C;&#x8FD9;&#x65F6;&#x5019;&#x5C31;&#x9700;&#x8981;&#x4F5C;&#x51FA;&#x4E00;&#x4E9B;&#x8C03;&#x6574;&#xFF0C;&#x6765;&#x7EE7;&#x7EED;&#x7EF4;&#x6301;&#x6211;&#x7684;&#x89C4;&#x5219;&#x3002;</p>
<p>&#x4EC0;&#x4E48;&#x60C5;&#x51B5;&#x4E0B;&#x4F1A;&#x7834;&#x574F;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x89C4;&#x5219;&#xFF0C;&#x4EC0;&#x4E48;&#x60C5;&#x51B5;&#x4E0B;&#x4E0D;&#x4F1A;&#x7834;&#x574F;&#x89C4;&#x5219;&#x5462;&#xFF1F;&#x6211;&#x4EEC;&#x4E3E;&#x4E24;&#x4E2A;&#x7B80;&#x5355;&#x7684;&#x6817;&#x5B50;&#xFF1A;</p>
<p>1.&#x5411;&#x539F;&#x7EA2;&#x9ED1;&#x6811;&#x63D2;&#x5165;&#x503C;&#x4E3A;14&#x7684;&#x65B0;&#x8282;&#x70B9;&#xFF1A;</p>
<p><img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x63D2;&#x5165;1.png" alt="img"></p>
<p>&#x7531;&#x4E8E;&#x7236;&#x8282;&#x70B9;15&#x662F;&#x9ED1;&#x8272;&#x8282;&#x70B9;&#xFF0C;&#x56E0;&#x6B64;&#x8FD9;&#x79CD;&#x60C5;&#x51B5;&#x5E76;&#x4E0D;&#x4F1A;&#x7834;&#x574F;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x89C4;&#x5219;&#xFF0C;&#x65E0;&#x9700;&#x505A;&#x4EFB;&#x4F55;&#x8C03;&#x6574;&#x3002;</p>
<hr>
<p>2.&#x5411;&#x539F;&#x7EA2;&#x9ED1;&#x6811;&#x63D2;&#x5165;&#x503C;&#x4E3A;21&#x7684;&#x65B0;&#x8282;&#x70B9;&#xFF1A;</p>
<p><img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x63D2;&#x5165;2.png" alt="img"></p>
<p>&#x7531;&#x4E8E;&#x7236;&#x8282;&#x70B9;22&#x662F;&#x7EA2;&#x8272;&#x8282;&#x70B9;&#xFF0C;&#x56E0;&#x6B64;&#x8FD9;&#x79CD;&#x60C5;&#x51B5;&#x6253;&#x7834;&#x4E86;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x89C4;&#x5219;4&#xFF08;&#x6BCF;&#x4E2A;&#x7EA2;&#x8272;&#x8282;&#x70B9;&#x7684;&#x4E24;&#x4E2A;&#x5B50;&#x8282;&#x70B9;&#x90FD;&#x662F;&#x9ED1;&#x8272;&#xFF09;&#xFF0C;&#x5FC5;&#x987B;&#x8FDB;&#x884C;&#x8C03;&#x6574;&#xFF0C;&#x4F7F;&#x4E4B;&#x91CD;&#x65B0;&#x7B26;&#x5408;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x89C4;&#x5219;&#x3002;</p>
<hr>
<h2 id="&#x63D2;&#x5165;&#xFF1A;">&#x63D2;&#x5165;&#xFF1A;</h2>
<p>&#x5C06;&#x9700;&#x8981;&#x63D2;&#x5165;&#x7684;&#x5143;&#x7D20;z&#x6309;&#x7167;&#x5E38;&#x89C4;&#x7684;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x8FDB;&#x884C;&#x63D2;&#x5165;&#xFF0C;&#x989C;&#x8272;&#x662F;&#x7EA2;&#x8272;&#x3002;</p>
<p>&#x7136;&#x540E;&#x9700;&#x8981;&#x5904;&#x7406;&#x5BF9;&#x4E8E;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x5B9A;&#x4E49;&#x8FDD;&#x53CD;&#x4E4B;&#x5904;&#x3002;</p>
<pre><code>a) &#x8DDF;&#x8282;&#x70B9;&#x662F;&#x7EA2;&#x8272;&#x7684;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x8BA9;&#x8DDF;&#x8282;&#x70B9;&#x53D8;&#x6210;&#x9ED1;&#x8272;&#x3002;

b) z &#x548C; z &#x7684;&#x7236;&#x8282;&#x70B9;&#x90FD;&#x662F;&#x7EA2;&#x8272;&#x7684;&#x3002;&#x5904;&#x7406;&#x8FD9;&#x79CD;&#x60C5;&#x51B5;&#xFF0C;&#x603B;&#x5171;&#x6709;&#x4E09;&#x79CD;
</code></pre><hr>
<h5 id="&#x516D;&#x79CD;&#x51B2;&#x7A81;&#x60C5;&#x51B5;&#x7684;&#x5904;&#x7406;&#xFF0C;&#x5047;&#x8BBE;&#x65B0;&#x52A0;&#x5165;&#x7684;&#x8282;&#x70B9;&#x662F;z&#xFF1A;">&#x516D;&#x79CD;&#x51B2;&#x7A81;&#x60C5;&#x51B5;&#x7684;&#x5904;&#x7406;&#xFF0C;&#x5047;&#x8BBE;&#x65B0;&#x52A0;&#x5165;&#x7684;&#x8282;&#x70B9;&#x662F;z&#xFF1A;</h5>
<ol>
<li><p>&#x7236;&#x8282;&#x70B9;&#x548C;&#x7236;&#x8282;&#x70B9;&#x7684;&#x5144;&#x5F1F;&#x8282;&#x70B9;&#x90FD;&#x662F;&#x7EA2;&#x8272;&#x7684;&#x5904;&#x7406;&#x65B9;&#x6CD5;</p>
<p> a) &#x5C06;z&#x7684;&#x7236;&#x8282;&#x70B9;&#x548C;&#x7236;&#x7684;&#x5144;&#x5F1F;&#x8282;&#x70B9;&#x90FD;&#x53D8;&#x6210;&#x9ED1;&#x8272;</p>
<p> b) &#x5C06;z&#x7684;&#x7956;&#x7236;&#x8282;&#x70B9;&#x53D8;&#x6210;&#x7EA2;&#x8272;</p>
<p> c) z&#x7684;&#x7956;&#x7236;&#x8282;&#x70B9;&#x53D8;&#x6210;&#x7EA2;&#x8272;&#x540E;&#xFF0C;&#x5FAA;&#x73AF;&#x5904;&#x7406;&#x51B2;&#x7A81;</p>
</li>
</ol>
<p><img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x63D2;&#x5165;3.png" alt="img"></p>
<hr>
<ol>
<li><p>z&#x7684;&#x7236;&#x8282;&#x70B9;&#x662F;&#x7EA2;&#x8272;&#xFF0C;&#x53D4;&#x53D4;&#x8282;&#x70B9;&#x662F;&#x9ED1;&#x8272;, z &#x7684;&#x7236;&#x8282;&#x70B9;&#x662F;&#x5DE6;&#x5B69;&#x5B50;&#xFF0C;z&#x662F;&#x53F3;&#x5B69;&#x5B50;&#x3002;</p>
<p> a) &#x5728;z&#x7684;&#x7236;&#x8282;&#x70B9;&#x6267;&#x884C;&#x5DE6;&#x79FB;&#x64CD;&#x4F5C;</p>
<p> b) &#x8BA9; z &#x7684;&#x5DE6;&#x5B69;&#x5B50;&#x6210;&#x4E3A;&#x65B0;&#x7684;&#x65B0;&#x63D2;&#x5165;&#x7684;z&#x8282;&#x70B9;&#xFF0C;&#x7EE7;&#x7EED;&#x5904;&#x7406;&#x51B2;&#x7A81;&#x3002;</p>
<p><img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x63D2;&#x5165;4.png" alt="img">   </p>
</li>
</ol>
<pre><code>z&#x7684;&#x7236;&#x8282;&#x70B9;&#x662F;&#x7EA2;&#x8272;&#xFF0C;&#x53D4;&#x53D4;&#x8282;&#x70B9;&#x662F;&#x9ED1;&#x8272;, z &#x7684;&#x7236;&#x8282;&#x70B9;&#x662F;&#x53F3;&#x5B69;&#x5B50;&#xFF0C;z&#x662F;&#x5DE6;&#x5B69;&#x5B50;&#x3002;

    a. &#x5728;z&#x7684;&#x7236;&#x8282;&#x70B9;&#x6267;&#x884C;&#x53F3;&#x79FB;&#x64CD;&#x4F5C;
    b. &#x8BA9; z &#x7684;&#x53F3;&#x5B69;&#x5B50;&#x6210;&#x4E3A;&#x65B0;&#x7684;&#x65B0;&#x63D2;&#x5165;&#x7684;z&#x8282;&#x70B9;&#xFF0C;&#x7EE7;&#x7EED;&#x5904;&#x7406;&#x51B2;&#x7A81;&#x3002;
</code></pre><hr>
<ol>
<li><p>z&#x7684;&#x7236;&#x8282;&#x70B9;&#x662F;&#x7EA2;&#x8272;&#xFF0C;&#x53D4;&#x53D4;&#x8282;&#x70B9;&#x662F;&#x9ED1;&#x8272;, z &#x7684;&#x7236;&#x8282;&#x70B9;&#x662F;&#x5DE6;&#x5B69;&#x5B50;&#xFF0C;z&#x662F;&#x5DE6;&#x5B69;&#x5B50;&#x3002;</p>
<p> a) &#x5728;z&#x7684;&#x7956;&#x7236;&#x8282;&#x70B9;&#x53F3;&#x79FB;&#x4E00;&#x6B21;
 b) &#x5C06;z&#x7684;parent&#x548C;z&#x7684;&#x5144;&#x5F1F;&#x8282;&#x70B9;&#x4EA4;&#x6362;&#x989C;&#x8272;</p>
</li>
</ol>
<p><img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x63D2;&#x5165;5.png" alt="img"> </p>
<p>z&#x7684;&#x7236;&#x8282;&#x70B9;&#x662F;&#x7EA2;&#x8272;&#xFF0C;&#x53D4;&#x53D4;&#x8282;&#x70B9;&#x662F;&#x9ED1;&#x8272;, z &#x7684;&#x7236;&#x8282;&#x70B9;&#x662F;&#x53F3;&#x5B69;&#x5B50;&#xFF0C;z&#x662F;&#x53F3;&#x5B69;&#x5B50;&#x3002;</p>
<pre><code>a) &#x5728;z&#x7684;&#x7956;&#x7236;&#x8282;&#x70B9;&#x5DE6;&#x79FB;&#x4E00;&#x6B21;
b) &#x5C06;z&#x7684;parent&#x548C;z&#x7684;&#x5144;&#x5F1F;&#x8282;&#x70B9;&#x4EA4;&#x6362;&#x989C;&#x8272;
</code></pre><hr>
<h2 id="&#x5220;&#x9664;&#xFF1A;">&#x5220;&#x9664;&#xFF1A;</h2>
<h4 id="&#x5148;&#x56DE;&#x987E;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x5220;&#x9664;&#x64CD;&#x4F5C;&#xFF1A;">&#x5148;&#x56DE;&#x987E;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#x7684;&#x5220;&#x9664;&#x64CD;&#x4F5C;&#xFF1A;</h4>
<ol>
<li><p>&#x5982;&#x679C;&#x5220;&#x9664;&#x7684;&#x8282;&#x70B9;&#x662F;z&#xFF0C;z&#x6CA1;&#x6709;&#x5B69;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x76F4;&#x63A5;&#x5220;&#x9664;</p>
</li>
<li><p>&#x5982;&#x679C;z&#x5305;&#x542B;&#x6709;&#x4E00;&#x4E2A;&#x5B69;&#x5B50;, &#x90A3;&#x4E48;&#x5C31;&#x5C06;z&#x53BB;&#x9664;&#x6389;&#xFF0C;&#x8BA9;z&#x7684;&#x8FD9;&#x4E2A;&#x5B69;&#x5B50;&#x66FF;&#x4EE3;&#x4E4B;&#x524D;z&#x7684;&#x4F4D;&#x7F6E;&#x3002;</p>
</li>
<li><p>&#x5982;&#x679C;z&#x5305;&#x542B;&#x4E24;&#x4E2A;&#x5B69;&#x5B50;&#xFF0C;&#x6211;&#x4EEC;&#x5C31;&#x53BB;&#x5BFB;&#x627E;&#x4E00;&#x4E2A;successor y &#x6765;&#x66FF;&#x4EE3;z&#xFF0C;&#x7136;&#x540E;&#x5C06;y&#x5220;&#x9664;&#x3002;&#x53C8;&#x662F;&#x4E00;&#x4E2A;&#x9012;&#x5F52;&#x7684;&#x8FC7;&#x7A0B;&#x3002;</p>
</li>
</ol>
<p>successor y &#x7684;&#x5BFB;&#x627E;&#x987A;&#x5E8F;&#xFF1A;</p>
<p>z&#x53F3;&#x5B69;&#x5B50;&#x7684;&#x6700;&#x5DE6;&#x8282;&#x70B9;</p>
<p>z&#x5DE6;&#x5B69;&#x5B50;&#x7684;&#x6700;&#x53F3;&#x8282;&#x70B9;</p>
<p>&#x4E3E;&#x4E2A;&#x4F8B;&#x5B50;&#xFF08;&#x5220;&#x9664;&#x8282;&#x70B9;&#x4E2D;&#x7684;32&#xFF09;&#xFF1A;
<img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x5220;&#x9664;1.png" alt="img"> </p>
<p><img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x5220;&#x9664;2.png" alt="img"> </p>
<p>&#x4E0B;&#x9762;&#x7684;&#x8FC7;&#x7A0B;&#x662F;&#x5220;&#x9664;&#x8282;&#x70B9;65:
<img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x5220;&#x9664;3.png" alt="img"> 
<img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x5220;&#x9664;4.png" alt="img"> </p>
<hr>
<h2 id="&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x5220;&#x9664;&#x64CD;&#x4F5C;&#xFF1A;">&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x5220;&#x9664;&#x64CD;&#x4F5C;&#xFF1A;</h2>
<ol>
<li>&#x5C31;&#x50CF;&#x662F;&#x666E;&#x901A;&#x7684;&#x641C;&#x7D22;&#x4E8C;&#x53C9;&#x6811;&#x4E00;&#x6837;&#x5220;&#x9664;&#x4E00;&#x4E2A;&#x8282;&#x70B9;z</li>
<li>&#x5982;&#x679C;z&#x5305;&#x542B;&#x6709;&#x4E24;&#x4E2A;&#x5B69;&#x5B50;&#xFF0C;&#x90A3;&#x4E48;&#x62F7;&#x8D1D;y&#x7684;&#x503C;&#x7ED9;z&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x4E0D;&#x8981;&#x590D;&#x5236;&#x989C;&#x8272;</li>
<li>&#x8BA9;y&#x6210;&#x4E3A;&#x9700;&#x8981;&#x88AB;&#x5220;&#x9664;&#x7684;&#x90A3;&#x4E2A;&#x8282;&#x70B9;</li>
<li>&#x5982;&#x679C; y &#x662F;&#x7EA2;&#x8272;&#x7684;&#xFF0C;&#x90A3;&#x4E48;&#x4E0D;&#x5F71;&#x54CD;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x5C5E;&#x6027;</li>
<li>&#x5982;&#x679C; y &#x662F;&#x9ED1;&#x8272;&#x7684;&#xFF0C;&#x90A3;&#x4E48;&#x5C31;&#x4E00;&#x5B9A;&#x4EA7;&#x751F;&#x4E86;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x51B2;&#x7A81;&#x3002;</li>
<li><p>&#x5047;&#x8BBE; x &#x662F; y &#x7684;&#x90A3;&#x4E2A;&#x552F;&#x4E00;&#x7684;&#x5B69;&#x5B50;&#x8282;&#x70B9;&#xFF0C;x&#x4E5F;&#x6709;&#x53EF;&#x80FD;&#x4E3A;&#x7A7A;&#x3002;</p>
<ul>
<li>&#x5047;&#x8BBE; x &#x662F; &#x7EA2;&#x8272;&#x7684;, &#x76F4;&#x63A5;&#x5C06;x&#x6539;&#x6210;&#x9ED1;&#x8272;&#x5373;&#x53EF;</li>
<li><p>&#x5047;&#x8BBE; x &#x662F;&#x9ED1;&#x8272;&#x7684;</p>
<ol>
<li><p>x&#x7684;&#x5144;&#x5F1F;&#x8282;&#x70B9; w &#x662F;&#x7EA2;&#x8272;&#x7684;&#x3002;</p>
<pre><code> &#x5DE6;&#x79FB;&#x4E00;&#x4F4D;&#xFF0C;&#x7136;&#x540E;&#x4FEE;&#x6539;B&#x548C;D&#x7684;&#x989C;&#x8272;&#xFF0C;&#x5C31;&#x53D8;&#x6210;&#x4E86; 2&#xFF0C;3&#xFF0C;4
</code></pre><p><img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x65CB;&#x8F6C;1.png" alt="img"></p>
</li>
<li><p>x&#x7684;&#x5144;&#x5F1F;&#x8282;&#x70B9; w &#x662F;&#x9ED1;&#x8272;&#x7684;&#xFF0C;w&#x7684;&#x4E24;&#x4E2A;&#x5B69;&#x5B50;&#x4E5F;&#x662F;&#x9ED1;&#x8272;&#x7684;&#x3002;w&#x53D8;&#x4E3A;&#x7EA2;&#x8272;
 &#x5C06; x &#x53D8;&#x6210;&#x5B83;&#x7684;&#x7236;&#x8282;&#x70B9;&#xFF0C;&#x7EE7;&#x7EED;&#x5FAA;&#x73AF;&#x7B2C;&#x516D;&#x6B65;</p>
</li>
</ol>
</li>
</ul>
</li>
</ol>
<p><img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x53D8;&#x8272;.png" alt="img"></p>
<pre><code>    3. x&#x7684;&#x5144;&#x5F1F;&#x8282;&#x70B9; w &#x662F;&#x9ED1;&#x7684;&#xFF0C;w&#x7684;&#x5DE6;&#x5B69;&#x5B50;&#x662F;&#x7EA2;&#x8272;&#x7684;&#xFF0C;&#x53F3;&#x5B69;&#x5B50;&#x662F;&#x9ED1;&#x8272;&#x7684;

        &#x53F3;&#x65CB;&#x8F6C;w&#xFF0C;&#x4EA4;&#x6362;w&#x548C;&#x5B83;&#x7684;&#x5B69;&#x5B50;&#x7684;&#x989C;&#x8272;&#x3002;&#x8F6C;&#x53D8;&#x6210;&#x4E86; 4
</code></pre><p><img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x53F3;&#x65CB;.png" alt="img"></p>
<pre><code>     4. x&#x7684;&#x5144;&#x5F1F;&#x8282;&#x70B9; w &#x662F;&#x9ED1;&#x8272;&#x7684;&#xFF0C;w&#x7684;&#x53F3;&#x5B69;&#x5B50;&#x662F;&#x7EA2;&#x8272;&#x7684;&#x3002;
        &#x4EE5;x&#x7684;&#x7236;&#x8282;&#x70B9;&#x4E3A;&#x57FA;&#x51C6;&#x5DE6;&#x65CB;&#x8F6C;&#xFF0C;&#x7136;&#x540E;&#x6539;&#x53D8;w&#x7684;&#x7684;&#x53F3;&#x5B69;&#x5B50;&#x7684;&#x989C;&#x8272;&#x3002;
</code></pre><p><img src="images/&#x7EA2;&#x9ED1;&#x6811;&#x53D8;&#x8272;2.png" alt="img">
    &#x4EE5;&#x4E0A;&#x5C31;&#x662F;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x5220;&#x9664;&#x64CD;&#x4F5C;&#x3002;</p>
<hr>
<h2 id="&#x7EA2;&#x9ED1;&#x6811;&#x5728;&#x54EA;&#x4E9B;&#x5730;&#x65B9;&#x88AB;&#x5B9E;&#x9645;&#x5E94;&#x7528;&#x5230;&#xFF1F;">&#x7EA2;&#x9ED1;&#x6811;&#x5728;&#x54EA;&#x4E9B;&#x5730;&#x65B9;&#x88AB;&#x5B9E;&#x9645;&#x5E94;&#x7528;&#x5230;&#xFF1F;</h2>
<p>&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x5E94;&#x7528;&#x6709;&#x5F88;&#x591A;&#xFF0C;&#x5176;&#x4E2D;JDK&#x7684;&#x7ED3;&#x5408;&#x7C7B;TreeMap &#x548C;TreeSet &#x5E95;&#x5C42;&#x5C31;&#x662F;&#x7EA2;&#x9ED1;&#x6811;&#x5B9E;&#x73B0;&#x7684;&#x3002;</p>
<hr>
<p>&#x5185;&#x5B58;&#x4E2D;&#x7684;&#x641C;&#x7D22;&#x6811;&#x662F;&#x7528;&#x7EA2;&#x9ED1;&#x6811;&#x6765;&#x5B9E;&#x73B0;&#x7684;&#x3002;
&#x5982;&#x679C;&#x5728;&#x5185;&#x5B58;&#x4E2D;&#x5B58;&#x50A8;&#x6570;&#x636E;&#xFF0C;&#x5C31;&#x7528;&#x5230;&#x4E86;&#x7EA2;&#x9ED1;&#x6811;&#x3002;</p>

                    
                    </section>
                
                
                </div>
            </div>
        </div>

        
        <a href="../树的实现/B+树.html" class="navigation navigation-prev " aria-label="Previous page: B+树"><i class="fa fa-angle-left"></i></a>
        
        
        <a href="../六大排序/六大基本排序.html" class="navigation navigation-next " aria-label="Next page: 六大基本排序"><i class="fa fa-angle-right"></i></a>
        
    </div>
</div>

        
<script src="../gitbook/app.js"></script>

    
    <script src="../gitbook/plugins/gitbook-plugin-search/lunr.min.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-search/search.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-sharing/buttons.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-fontsettings/buttons.js"></script>
    

<script>
require(["gitbook"], function(gitbook) {
    var config = {"highlight":{},"search":{"maxIndexSize":1000000},"sharing":{"facebook":true,"twitter":true,"google":false,"weibo":false,"instapaper":false,"vk":false,"all":["facebook","google","twitter","weibo","instapaper"]},"fontsettings":{"theme":"white","family":"sans","size":2}};
    gitbook.start(config);
});
</script>

        
    </body>
    
</html>
